package code.starivan.others;

import code.starivan.others.ListNode;

/**
 * Created by Ivan on 2015/9/8.
 */
public class TestLinkedList<T> {
    private int size; //size of list.

    private transient ListNode<T> header=new ListNode<T>(null, null, null); //header of list

    //use inner class to define node in list
    private static class ListNode<T> {
        public ListNode(T data){
            this.data = data;
            this.prev = null;
            this.next = null;
        }
        public ListNode(T data, ListNode<T> prev, ListNode<T> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
        public T data; //data
        public ListNode<T> prev; //pre pointer
        public ListNode<T> next; //next pointer
    }

    public TestLinkedList () {
        header.next = header.prev = header;
    }

    //clear list.
    public void clear () {
        ListNode<T> e = header.next;
        while (e != header) {
            ListNode<T> next = e.next;
            e.next = e.prev = null;
            e.data=null;
            e=next;
        }

        header.next=header.prev=header;
        size=0;
    }

    //size of list.
    public int size() {
        return size();
    }

    //check empty
    public boolean isEmplty() {
        return size == 0;
    }

    //add element
    public boolean add(T e) {
        add(size(), e);
        return true;
    }

    public void add(int index, T e) {
        addBefore(getNode(index), e);
    }

    //add element before the node.
    private void addBefore (ListNode<T> node, T e) {
        ListNode<T> newNode = new ListNode<T>(e, node.prev, node);
        newNode.prev.next = newNode;
        node.prev = newNode;
    }

    //get data by index
    public T get(int index) {
        return getNode(index).data;
    }

    //set data to a node by index, and return the old data.
    public T set(int index, T newData) {
        ListNode<T> oldNode = getNode(index);
        T oldData = oldNode.data;
        oldNode.data = newData;
        return oldData;
    }

    //remove a node by index, and return the data
    public T remove(int index) {
        return remove(getNode(index));
    }

    private T remove(ListNode<T> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        return node.data;
    }

    //get a node by index
    private ListNode<T> getNode(int index) {
        ListNode<T> node;

        if(index <0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }

        if(index < size()/2) {
            node = header.next;
            for (int i = 0;i < index;i++) {
                node = node.next;
            }
        }else {
            node = header.prev;
            for (int i = size()-1;i>index;i--) {
                node = node.prev;
            }
        }
        return node;
    }
}
